package tree;

import java.util.Stack;

public class RecursivelyBinaryTree {
    private static class Node {
        Integer data;
        Node left;
        Node right;

        public Node(Integer data) {
            this.data = data;
        }
    }

    private static void Recursive(Node node) {
        if (node == null) {
            return;
        }
        Recursive(node.left);
        Recursive(node.right);
    }

    private static void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        preOrder(node.left);
        preOrder(node.right);
    }

    private static void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.data);
        inOrder(node.right);
    }

    private static void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }

    /*
    压栈弹栈的方式先序遍历二叉树
     */
    private static void pre(Node node) {
        Stack<Node> stack = new Stack<>(); //创建一个栈
        stack.push(node);        //把根压入栈顶
        while (!stack.isEmpty()) {      //只要栈不为空就一直压栈弹栈
            node = stack.pop();       //  把根节点弹出 每次都是弹根节点
            System.out.println(node.data); //弹根 打印
            if (node.right != null) {         //只要有右节点就先把右节点全部压入栈
                stack.push(node.right);
            }
            if (node.left != null) {          //右孩子压完了每次弹根实现先序
                stack.push(node.left);
            }

        }
    }

    private static void levelOrder(Node node){
        SuperArray<Node>superArray = new SuperArray<>();
        superArray.addToHead(node);
        while (superArray.size() > 0){
            Node select = superArray.select(superArray.size() - 1);
            superArray.del(superArray.size() - 1);
            System.out.println(select.data);
            if(select.left!=null){
                superArray.addToHead(select.left);
            }
            if(select.right!=null){
                superArray.addToHead(select.right);
            }

        }
    }



    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        levelOrder(root);
    }
}
